1. Field of the Invention
The present invention relates to scheduling data transfer between nodes in a communications network, and, more particularly, to generating a schedule using graphs.
2. Description of the Related Art
Wavelength Division Multiplexing (WDM) is commonly employed for optical transport networks. WDM technology is applied to both optical ring architectures and mesh networks. A transport WDM optical ring consists of a number N of nodes connected through optical links in a ring topology. Each node can add or drop one or more wavelengths, and each node passes-through the rest of the wavelengths. In many WDM systems, a dedicated wavelength is assigned between any two nodes requiring a communication path, and traffic management is performed with wavelength granularity.
The cost of each WDM node is determined by: i) the number of optical transmitters and receivers corresponding to the number of wavelengths that are added/dropped at each node and ii) the circuitry and memory bandwidth required to process traffic that is added/dropped at each node. In the worst case, which is observed in the case of uniform traffic demands, every node requires a communication path to every other node in the ring, and each node must support at least N transmitters and N receivers.
One problem associated with WDM optical rings is that the granularity of traffic demands is determined by the wavelength granularity, which leads to inefficient resource utilization. If traffic demands are lower than the bandwidth available on a wavelength, then the point-to-point (node-to-node) wavelengths are underutilized. For example, if each wavelength supports a data rate (bandwidth) of 10 Gbp/s, and traffic demand rates are 1 Gbps each, then 90% of the available wavelength bandwidth remains unused.
To increase resource utilization, a WDM optical ring can be implemented with electronic grooming devices. With electronic grooming devices, a wavelength is i) dropped at a node and demultiplexed and/or ii) multiplexed with local traffic and added back to the ring. Although the number of separate wavelength transmitters and/or receivers can be reduced with electronic grooming as opposed to optical grooming, grooming devices add to the network cost. This network cost can be high in terms of equipment cost, added cost of controlling additional devices, sparing, and network management support.
Alternatively, grooming or packet multiplexing services may include optical technologies that are based on optical packet or burst switching. Packet or burst switching allows for sharing of a wavelength between multiple transmitters/receivers in the optical domain and without the need for additional electronic devices. In ring networks, three methods can be used for switching. The first method employs tunable transmitters and fixed receivers (TTFR). With the TTFR method, traffic is transmitted in terms of packets or bursts, and communication between two nodes occurs by tuning the wavelength of the transmitter to the fixed wavelength associated with the receiver. The second method employs fixed transmitters and tunable receivers (FTTR). With the FTTR method, traffic is transmitted in terms of packets or bursts, and communication between two nodes is on a fixed wavelength of the transmitter. The receiver tunes to the wavelength it wishes to receive (equivalent to a “broadcast-and-select” architecture). A third method allows both tunable transmitters and tunable receivers (TTTR), thus providing further flexibility.
Implementing TTFR, FTTR, and TTTR architectures without substantial loss of bandwidth due to slow tuning times of the optical components requires fast tunable lasers in the transmitter or fast tunable optical detectors in the receiver. Recent developments in optical technologies have demonstrated fast tunable lasers with less than 50 ns tuning time. Tuning time might be further reduced to less than Ins using integrated multi-frequency lasers (MFLs).
A requirement of operation of a WDM optical ring with the TTFR method is that data from two transmitters cannot arrive at the same receiver at the same time, since a given transmitter sends only to one receiver at any given burst (or “time-slot”). When the data from two transmitters arrives at the same receiver, a conflict arises and data is corrupted at the receiver. Propagation delay may cause packets on a given wavelength sent from nodes distant to a given node to overlap packets that are sent from nearer nodes which the given node is attempting to receive. Similar conflicts arise in FTTR and TTTR rings. Therefore, a “contention resolution” mechanism is necessary to prevent such conflicts.
FIGS. 1A, 1B, and 1C illustrate the problem of scheduling in a TTFR ring with long propagation delays. FIGS. 1A, 1B, and 1C each show an exemplary WDM optical ring 100 having three nodes, N1, N2, and N3, where the three nodes are interconnected by equidistant links and where each node/link supports 3 wavelengths. Each link length corresponds to a 1 μs propagation delay (e.g., resulting from a 330 m-distance fiber). WDM optical ring 100 includes a simple traffic matrix that describes the required transfer of packet or burst traffic data between a given pair of network nodes. A traffic matrix is also known as a demand matrix or rate matrix.
For WDM optical ring 100, the traffic matrix specifies every node requires capacity equal to 50% of the wavelength bandwidth to communicate with the other two nodes in the ring. In other words, during one time-slot the node tunes the transmitter to send on one wavelength to one node, and in the next time-slot the node tunes the transmitter to send on the other wavelength to the other node. For WDM optical ring 100, the time-slot (burst) length is 1 μs (i.e., the time-slot length equals the propagation delay). A simple TDMA scheduling of the traffic matrix that achieves this traffic distribution under zero propagation delays is given in Table 1.
TABLE 1NodeDestination NodeDestination NodeDestination NodeNumberIn Time-Slot 1In Time-Slot 2In Time-Slot 3123223133121
Referring to FIG. 1A, at time-slot 1, node N1 transmits packet 101 to node N2, node N2 transmits packet 102 to node N3, and node N3 transmits packet 103 to node N1. Referring to FIG. 1B, at time-slot 2, packets 101, 102, and 103 have reached their destination nodes N2, N3, and N1, respectively. In addition, at time-slot 2, node N1 transmits packet 111 to node N3, node N2 transmits packet 112 to node N1, and node N3 transmits packet 113 to node N2. Thus, during time-slot 2, each packet that a node generates now must traverse one intermediate node before receipt at the destination node.
Referring to FIG. 1C, at time-slot 3, a conflict arises. At time-slot 3, intermediate node N1 attempts to forward packet 113 to the corresponding destination node N2, intermediate node N2 attempts to forward packet 111 to the corresponding destination node N3, and intermediate node N3 attempts to forward packet 112 to the corresponding destination node N1. However, at time-slot 3, the scheduling matrix dictates that node N1 transmit packet 121 to node N2, node N2 transmit packet 122 to node N3, and node N3 transmit packet 123 to node N1. Therefore, at time-slot 3, all three nodes N1, N2, and N3 are attempting to transmit packet data in the same wavelength that is already used by a previous node. For example, node N1 attempts to transmit packet 121 to node N2 while also attempting to forward packet 113 to node N2. The contention illustrated in FIGS. 1A, 1B, and 1C shows that simple scheduling, such as is typically defined in TDMA networks, does not provide 100% throughput in a TTFR ring with large propagation delays.
Two different methods of the prior art might be employed for contention resolution in WDM packet-switched rings. One method is based on per-wavelength power detectors, and the other method is based on an independent control channel. In both of these methods, each node detects the wavelengths that are currently passing through the node, and each node selects an available wavelength (and thus destination) for transmission based on a Medium Access Protocol (MAC).
Contention resolution for networks with propagation delays is not restricted to WDM optical ring networks. In general, contention resolution of the prior art may be extended to other networks of nodes employing switching where scheduling of a traffic matrix accounts for propagation delays.